import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MyBinaryTree {
    static class Node {
        public char value;
        public Node left;
        public Node right;
        public Node() {
        }
        public Node(char value) {
            this.value = value;
        }
    }
    public int size;
    public int leafSize;
    public Node create(){
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = F;
        return A;
    }
    public Node create2(){
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        return A;
    }
    public Node create3(){
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('G');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = F;
        return A;
    }
    public Node create4(){
        Node B = new Node('B');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        B.left = D;
        B.right = E;
        E.right = F;
        return B;
    }
    public Node create5(){
        Node E = new Node('E');
        Node F = new Node('F');
        Node H = new Node('H');
        E.right = F;
        F.right = H;
        return E;
    }
    //判断是否为空
    public boolean isNull(Node head){
        if (head == null){
            return true;
        }else {
            return false;
        }
    }
    //不好
    //求长度
    public int size1(Node head){
        if(head == null){
            return 0;
        }
        size++;
        size1(head.left);
        size1(head.right);
        return size;
    }
    public int size2(Node head){
        if(head == null){
            return 0;
        }
        /*count++;
        count += size2(head.left);
        count += size2(head.right);*/

        return +1 + size2(head.left) + size2(head.right);
    }
    public int leafSize1(Node head){
        if (head == null){
            return 0;
        }
        if (head.left == null && head.right == null){
            leafSize++;
        }
        leafSize1(head.left);
        leafSize1(head.right);
        return leafSize;
    }
    public int leafSize2(Node head){
        if (head == null){
            return 0;
        }
        if (head.left == null && head.right == null){
            return 1;
        }
        return leafSize2(head.left) + leafSize2(head.right);
    }
    public int leafK(Node head,int k){
        if (head == null || k < 1){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return leafK(head.left,k-1) + leafK(head.right,k-1);
    }
    public int treeHeight(Node head){
        if (head == null){
            return 0;
        }
        int x = treeHeight(head.left);
        int y = treeHeight(head.right);
        return Math.max(x,y) + 1;
    }
    public boolean charFind(Node head,char x){
        if (head == null){
            return false;
        }
        if (head.value == x){
            return true;
        }
        return charFind(head.left,x) || charFind(head.right,x);
    }
    public Node charFind2(Node head,char x){
        if (head == null){
            return null;
        }
        if (head.value == x){
            return head;
        }
        Node ret =charFind2(head.left,x);
        if (ret != null){
           return ret;
        }
        ret = charFind2(head.right,x);
        if (ret != null){
            return ret;
        }
        return null;
    }
    public void puDisply(Node head, Queue<Node> queue){
        if (head == null){
            return;
        }
        System.out.print(head.value + " ");
        if (head.left != null){
            queue.offer(head.left);
        }
        if (head.right != null){
            queue.offer(head.right);
        }
        if (!queue.isEmpty()) {
            puDisply(queue.poll(),queue);
        }
    }
    public void puDisply2(Node head){
        if (head == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()){
            Node ret = queue.poll();
            System.out.print(ret.value + " ");
            if (ret.left != null){
                queue.offer(ret.left);
            }
            if (ret.right != null){
                queue.offer(ret.right);
            }
        }
    }
    public List<List<Character>> puDisply3(Node node){
        if (node == null){
            return null;
        }
        List<List<Character>> ret = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            List<Character> ret1 = new ArrayList<>();
            int size = queue.size();
            while (size > 0){
                Node tmp = queue.poll();
                size--;
                ret1.add(tmp.value);
                if (tmp.left != null){
                    queue.offer(tmp.left);
                }
                if (tmp.right != null){
                    queue.add(tmp.right);
                }
            }
            ret.add(ret1);
        }
        return ret;
    }
    public void AdisPlay(Node head){
        if(isNull(head)){
            return;
        }
        System.out.print(head.value + " ");
        AdisPlay(head.left);
        AdisPlay(head.right);
    }
    public void BdisPlay(Node head){
        if(isNull(head)){
            return;
        }
        BdisPlay(head.left);
        System.out.print(head.value + " ");
        BdisPlay(head.right);
    }
    public void CdisPlay(Node head){
        if(isNull(head)){
            return;
        }
        CdisPlay(head.left);
        CdisPlay(head.right);
        System.out.print(head.value + " ");
    }
    //判断是否是完全二叉树
    public boolean isfull(Node head){
        if (head == null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()){
            Node tmp = queue.poll();
            if (tmp == null){
                break;
            }else {
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }
        }
        /*int size = queue.size();
        for (int i = 0; i < size; i++) {
            if (queue.poll() != null){
                return false;
            }
        }*/
        while (!queue.isEmpty()){
            if (queue.poll() != null){
                return false;
            }
        }
        return true;
    }
    //判读是否是相同的二叉树
    public boolean isSame(Node head1,Node head2){
        if (head1 == null && head2 == null){
            return true;
        }
        if ((head1 == null && head2 != null) || (head1 != null && head2 == null) || (head1.value != head2.value)){
            return false;
        }
        /*if (!isSame(head1.left,head2.left)){
            return false;
        }
        if (!isSame(head1.right,head2.right)){
            return false;
        }
        return true;*/
        return isSame(head1.left,head2.left) && isSame(head1.right,head2.right);
    }
    //判断一颗树是否包含另一棵树
    public boolean isInclude(Node head1,Node head2){

        /*if (root == null && subRoot == null){
            return true;
        }
        if ((root == null && subRoot != null) || (root != null && subRoot == null)){
            return false;
        }
        if (root.value != subRoot.value){
            return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
        }else {
            return isSame(root,head2);
        }*/

        if (head1 == null && head2 == null){
            return true;
        }
        if (head1 == null  || head2 == null){
            return false;
        }
        if (isSame(head1,head2)){
            return true;
        }
        if (isInclude(head1.left,head2) || isInclude(head1.right,head2)){
            return true;
        }
        return false;
    }
    public int treeHeight2(Node head){
        if (head == null){
            return 0;
        }
        int x = treeHeight(head.left);
        int y = treeHeight(head.right);
        if (Math.abs(x-y) > 1 || x == -1 || y == -1){
            return -1;
        }else {
            return Math.max(x,y) + 1;
        }
    }
    public boolean isBalance(Node head){
        if (head == null){
            return true;
        }
        int x = treeHeight(head.left);
        if (x == -1){
            return false;
        }
        int y = treeHeight(head.right);
        if (y == -1){
            return false;
        }
        int z = x > y ? x - y : y - x;
        if(z > 1){
            return false;
        }
        /*if (!isBalance(head.left)){
            return false;
        }
        if (!isBalance(head.right)){
            return false;
        }*/
        return true;
    }
    public int treeHeight3(Node root){
        if (root == null){
            return 0;
        }
        if (root.left.value != root.right.value){
            return -1;
        }
        int x = treeHeight3(root.left);
        int y = treeHeight3(root.right);
        if (x != y){
            return -1;
        }
        if (treeHeight3(root.left) == -1){
            return -1;
        }
        if (treeHeight3(root.right) == -1){
            return -1;
        }
        return Math.max(x,y)+1;
    }
    public boolean tmpValue(Node head1,Node head2){
        if (head1 == null && head2 == null){
            return true;
        }

        if ((head1 == null && head2 != null) || (head1 != null && head2 == null) || (head1.value != head2.value)){
            return false;
        }
        if (!tmpValue(head1.left,head2.right)){
            return false;
        }
        if (!tmpValue(head1.right,head2.left)){
            return false;
        }
        return true;
    }
    public boolean isSymmetric(Node root){
        if (root == null){
            return true;
        }
        return tmpValue(root.left, root.right);
    }
}
